1. Field of the Invention
The present invention generally relates to methods for finding a resource and a service in network and relay node apparatuses, and more particularly to a method for finding a resource and a service in network and a relay node apparatus, in which a plurality of nodes provides resources and services maintained thereby.
2. Description of the Related Art
Conventionally, the Internet is a network mainly for personal computers (PCs) and workstations. Recently, accompanying with an evolution of minimized information terminals including a mobile phone and wide use of state-of-the-art IC chips, a communication called a ubiquitous communication that can communicate to any terminal anywhere and anytime, regardless of a type of a terminal is attracting attention as a communication form for the next generation.
In a network in which various nodes are mutually connected, since the number of resources and services and an amount of resources and services provided by various nodes becomes greater, a mechanism to effectively find a resource and a service becomes important. In a scope of this specification and claims, a resource means the resource included in hardware or a memory of any node, and a service means an intangible material provided by combining resources so as to bring a benefit to a user.
In the ubiquitous communication, requirements needed to find a resource or a service maintained by each node will be shown as follows:
A first requirement is to find a resource and a service maintained by any node. Conventionally, a client/server model, which defines a clear distinction between one node providing the resource and the service and another node receiving the resource and the service form the one node, is mainly applied. Accordingly, a technology for searching for a server as a search subject to receive the service and the resource has been widely used. For example, a conventional search engine for searching for homepages targets a Web server to implement. However, in the ubiquitous network, it is not easy to simply define a clear distinction between nodes such as in the client/server model. Thus, it is required to find the resource and the service provided by any node.
A second requirement is to have scalability with respect to the number of nodes. In the ubiquitous network, a node connected to a network is not limited to a PC (Personal Computer) but can be a node having an IC chip. Thus, a technology having scalability with respect to the number of nodes is required.
A third requirement has a lower load with respect to the network in a process for finding the resource or the service through the network. It is difficult to provide a bandwidth of the network proportional to the enormous number of nodes in a ubiquitous communication. Thus, it is required to suppress the load to the network in the process for finding the resource or the service through the network.
A fourth requirement is to have a fault-tolerance. In the ubiquitous communication, not only nodes securing sufficient reliability such as a conventional server provides the resource and the service. Thus, it is required to be a technology based on the premise that there is a node which cannot provide the resource and the service stably for a long time (for many days) since a connection to the network and an OS of the node are not stable.
A fifth requirement is to support a plurality of nodes providing the same resource or the same service. In the ubiquitous communication, the plurality of nodes may provide the same resource or the same service. Thus, it is required to select one node from a node group providing the same resource or the same service and provide a user a search result.
Existing search technologies for searching for resources and services are classified into as follows:
A centralization type is a search technology in that any node collects information concerning resources and services provided by any server and manages in a database beforehand, and the resources and the services are found. In general, a node called “search site” or “search engine” collects the information concerning the resources and the services. A search site searches for the database by using a keyword input by a user, provides information concerning nodes publishing the resources and the services related to the keyword. It should be noted that the centralization type is a type of a registration of a node providing the resource and the service, and can be classified into a robot type or a manual type.
The robot type is a search technology in that a server autonomously collects information concerning the resources and the services in the network by using a program called “robot”.
The manual type is a search technology in that the user or a server administrator for a search registers a location identification identifying a location of each of the resources and the service to a server managed by the server administrator and a keyword related thereto.
A distribution type is a search technology to inquire nodes in the network for each inquiry which node has the resource and the service. The distribution type does not require any database such as the centralization type. The distribution type is mostly used by a file sharing application such as Gnutella™, WinMix™, and a like. Since the resource and the service provided by any node can be searched from any node, the distribution type is called a peer-to-peer type (PtoP type).
A hybrid type is a search technology positioned between the centralization type and the distribution type, and periodically exchanges the resource and the service published by each node between nodes. In the distribution type, it is difficult to satisfy the first requirement previously described. Accordingly, the following discussion will focus on the distribution type and the hybrid type.
A procedure for finding the resource and the service in the distribution type has not been standardized. In practice, most applications of the distribution type are based on a procedure of Gnutella™. Thus, in the following, an operation example of Gnutella™ will be shown.
Gnutella™ is application software for exchanging files individually through the network. Thus, in Gnutella™, the resource and the service is handled as a file. PCs of users of Gnutella™ are mutually connected through the network, and each user opens a list of files to share with other users through the network. In a case of searching for a file on Gnutella™, files opened by nodes other than its own node and meeting a condition are extracted, and then the own node searching for the file can download the file as the resource directly from a node having the file as the resource.
The procedure for finding the resource and the service in the distribution type will be described with reference to FIG. 1. When a query as a request for finding a file is sent to a host computer connected to the network, the query (request) is sequentially relayed to a next neighbor node. A host computer having the file being a requested subject replies a hit response. Then, it is realized to find the file.
In FIG. 1,
(1) A query command for finding a file is sent to a neighbor node.
(2) This query command (simply called query) is sequentially relayed to a next neighbor node.
(3) A node having the file replies with a hit response.
(4) The hit response is sequentially traversed in accordance with a reversed path of the query, and responds to a node being a sender of the query.
(5) The node being the sender of the query connects to any one of nodes that reply with the hit response, in accordance with TCP (Transmission Control Protocol).
(6) The node being the sender of the query sends a request for obtaining the file.
(7) Contents of the file is transmitted to the node being the sender of the query.
In the above (2), in order to prevent from relaying the query infinitely, since Gnutella™ includes a concept of TTL (Time To Live) as well as IP (Internet Protocol), the query is discarded after the query is transferred to a next neighbor node more than or equal to a predetermined number of nodes.
It is realized to find the resource or the service in Gnutella™ by broadcasting the query by a bucket brigade. Thus, the following problems are raised.
Problem 1: the number of nodes to search is enormous. The number of nodes searching for the resource or the service is increased in geometrical progression. This problem is caused because information concerning the resource or the service provided by nodes is not exchanged to each other among the nodes. As a result, in a case in that a node receiving the query does not have the resource or the service as a search subject, since the node does not have information showing to which neighbor node the query is transferred, it is needed to broadcast all over the neighbor nodes in the network. Accordingly, the second requirement is not satisfied.
Problem 2: a bandwidth of the network is used unnecessarily. The query is broadcast to neighbor nodes and then the number of nodes to broadcast the query is increased in geometrical progression for each path to the neighbor nodes. However, the node originally sending the query sends the request for obtaining the file (obtain command) to one node at most, and other queries (for example, queries toward bottom three nodes of four nodes at a right side in FIG. 1) unnecessarily consume the bandwidths of the network. Thus, the third requirement is not satisfied.
Problem 3: a mechanism of the fault tolerance is not implemented. Thus, the fourth requirement is not satisfied.
The hybrid type has a feature of periodically exchanging information concerning the resource and the service provided by each of the nodes. Since there is no standard in an actual state, an operation example of the hybrid type will be shown by Flapps (Forwarding Layer for Application-level Peer-to-Peer Services) offered by UCLA (University of California, Los Angeles) in U.S.A.
The hybrid type exchanges “name” (file name, URL (Uniform Resource Locator), and a like) of the resource and the service opened by the node and path information toward the node among nodes. Based on a result of a path exchange, each of the nodes transmits the resource or the service requested by a query to a node sending the query.
Two phases are included in finding the resource and the service in the hybrid type. A first phase is a phase of distributing identification of the resource or the service (hereinafter, called name path information). A second phase is a phase of finding the resource and the service based on a request sent from a node.
FIG. 2 is a diagram showing a sequence flow for explaining a distribution phase of the name path information according to the present invention. First, an environment being assumed will be described. Both a node B and a node C open a file (resource) called “resource/music/rock.mp3”. A node A, the node B, the node C, and relay nodes 1 through 6 are mutually communicable by indicating an IP address. The relay node may be a terminal such as a PC or may be a network device such as a router to which an additional function is provided. The name path information is exchanged periodically among the nodes A, B, and C, and the relay nodes 1 through 6. In sequence flows after FIG. 2, “IP-A” represents an IP address of the node A, and IP addresses of the other nodes are represented in the same manner. The name path information exchanged between the nodes is described in an order of a source IP, a destination IP, a command name, a resource name, and a next hop IP.
In FIG. 2,
(1) The node C sends a frame showing that a resource identified by “resource/music/rock.mp3” is opened, to a neighbor node (relay node 5) ((1) in FIG. 2).
(2) The relay node 5 identifies “name path information” from a command name of the frame being received, decomposes a character string of the resource name by each delimiter (“/” in this case) that is defined beforehand, and creates a search tree. After that, the relay node 5 informs a neighbor node (relay node 4) that the relay node 4 can achieve “resource/music/rock.mp3” by passing through the relay node 5 itself, that is, the relay node 4 can achieve a node (node C) opening “resource/music/rock.mp3” by transferring a query sent from any node toward the relay node 5 ((2) in FIG. 2).(3) A process of the relay node 4 is the same as that described in (2) ((3) in FIG. 2).(4) Similar to (1), the node B informs the relay node 6 being a neighbor node that the node B opens “resource/music/rock.mp3” ((a) in FIG. 2). Also, similar to (2), after the relay node 6 creates the search tree, the relay node 3 informs the name path information to the relay node 3 ((b) in FIG. 2).(5) The relay node 3 receives the name path information concerning “resource/music/rock.mp3” from both the relay nodes 4 and 6. As a result, the search tree showing IP-6 and IP-4 as a search result as shown in FIG. 2 is created in the relay node 3. The relay node 3 determines to select IP-6 or IP-4 as the search result by using an algorithm (not shown) (for example, select alternately).(6) In the following, the relay node 3 and relay node 2 conduct a process similar to (2), so that the name path information is relayed to the relay node 2 and then to the relay node 1 ((4) and (5) in FIG. 2).
As described above, each name of the resources opened by the node B and the node C and the path information are exchanged among the relay nodes 1 through 6.
Next, a sequence flow of a find phase of the service is shown in FIG. 3.
In FIG. 3:
(1) The node A sends a query frame for requesting to find a node having “resource/music/rock.mp3” to the network ((1) in FIG. 3).
(2) The relay node 1 identifies “query” from the command name of the frame being received, decomposes a character string of the resource name for each delimiter (“/” in this case) which is defined beforehand, and searches for the search tree in an order of keys obtained by decomposing the resource name.(3) A next hop shown by a search result is the relay node 3. Thus, the relay node 1 transfers the query toward the relay node 2.(4) The relay node 2 conducts a process similar to that described in (2) and (3), and transfers the query toward the relay node 3.(5) The relay node 3 conducts a process similar to that described in (2). In this case, there are the relay nodes 4 and 6 as a next hop. The relay node 3 selects one of the relay nodes 4 and 6 by using an algorithm (not shown) (for example, select alternately). It is assumed that the relay node 3 selects the relay node 6. The relay node 3 conducts a process similar to that described in (3), and transfers the query toward the relay node 6 ((4) in FIG. 3).(6) The relay node 6 conducts a process similar to that described in (2) and (3), and transfers the query toward the node B ((5) in FIG. 3).(7) Since the node B has “resource/music/rock.mp3” as the resource being a find subject in itself, the node B identifies a “sender node IP” field, establishes a TCP connection to IP-A (node A), and stars a file transfer ((6) in FIG. 3).
Japanese Laid-open Patent Application No. 10-70552 discloses that a node sends a reply packet showing a correspondence between its own closed address and its own extended address with respect to a node which generated an information packet, and the node which generated an information packet includes contents of the replay packet received from the node which sent the relay packet, into its own routing table. Thus, a routing table for routing by the extended address can be generated.
Moreover, Japanese Laid-open Patent Application No. 2001-203739 discloses a path search frame is generated by using an address of the unknown destination and an own address of a relay apparatus when a receive frame shows an unknown destination, and the received frame is sent toward a sender sending a response frame when the response frame being replied from the relay apparatus which finds a destination in response to the path search frame is received.
The hybrid type conducts the find procedure for finding the resource and the service being distributed by exchanging information (name path information) concerning the resource and the service maintained in each node. Thus, when a state of providing the resource or the service by the node is changed (for example, when it becomes impossible to provide the resource or the service), the find procedure for finding the resource and the service cannot be provided stably in the network until the name path information for informing this change is transferred to a relay node group.
That is, a part of the relay group is not informed that the resource or the service is not provided and another part of the relay group is informed. As a result, an inconsistency of the name path information occurs, that is, the network becomes unstable, hereinafter, called “unstable state”. As described above, the unstable state may occur in the ubiquitous communication that does not ensure stability of the node.
In the network under the unstable state, the query frame might have been already distributed to a node that does not provide the resource or the service (hereinafter, called “closed node”), and the query frame may not be arrived to a node that provides the resource or the service. Hereinafter, a frame that is not distributed to the node providing the resource or the service is called “not-arrived frame”. There are problems to be solved as follows:
Problem 1 to be solved: as an objective to eliminate the not-arrived frame, the network is required to autonomously detect a path toward the closed node and to transfer the query frame being sent to the closed node toward another node.
Problem 2 to be solved: as another objective to suppressing the unstable state, it is needed to inform each of the relay nodes that a node becomes the closed node, without waiting a periodical name path exchange.